//
// Created by liushuai on 2020/5/5.
//
#include "dfs_tree.h"
#include <vector>

void dfs_tree_stack(TreeNode* root)
{
    std::stack<TreeNode*> s;
    TreeNode* current_node = root;
    s.push(root);
    while (current_node)
    {
        TreeNode* pop_node = current_node;
        if (s.size() > 0)
            s.pop();
        std::cout << "访问节点:" << pop_node->val;
        if (pop_node->right)
            s.push(pop_node->right);
        if (pop_node->left)
            s.push(pop_node->left);
        if (s.size() > 0)
            current_node = s.top();
        else
            current_node = nullptr;
    }
}

void dfs_travel_layer(TreeNode* root, int layer, std::vector<std::vector<int>>& result)
{
    if (root)
    {
        // 不能直接push_back，通过判断result的大小获取层数否则层result的size可能会大于层数
        if (result.size() < layer + 1)
            result.push_back(std::vector<int>());
        result.at(layer).push_back(root->val);
        dfs_travel_layer(root->left, layer + 1, result);
        dfs_travel_layer(root->right, layer + 1, result);
    }
}
std::vector<std::vector<int>> dfs_travel_layer(TreeNode* root)
{
    std::vector<std::vector<int>> result;
    dfs_travel_layer(root, 0, result);
    return result;
}
int maxDepth(TreeNode* root)
{
    if (!root)
        return 0;
    else
    {
        int left_size = maxDepth(root->left) + 1;
        int right_size = maxDepth(root->right) + 1;
        int result = left_size > right_size ? left_size : right_size;
        return result;
    }
}
#include "bfs_tree.h"
void bfs_queue(TreeNode* root)
{
    std::queue<TreeNode*> q;
    TreeNode* current_node = root;
    q.push(current_node);
    while (q.size() > 0)
    {
        current_node = q.front();
        std::cout << "访问节点：" << current_node->val;
        q.pop();
        if (current_node->left)
            q.push(current_node->left);
        if (current_node->right)
            q.push(current_node->right);
    }
}
std::vector<std::vector<int>> travel_layer(TreeNode* root)
{
    std::queue<TreeNode*> q;
    std::vector<std::vector<int>> result;
    if (root)
        q.push(root);
    while (q.size())
    {
        std::vector<int> layer;
        int node_nums = q.size(); //        分层打印的关键是需要知道当前队列中节点的个数（叶子节点的数目）
        for (int i = 0; i < node_nums; i++)
        {
            TreeNode* node = q.front();
            q.pop();
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
            layer.push_back(node->val);
        }

        result.push_back(layer);
    }
    return result;
}
